package lc20240604;

import java.util.*;
/**
  * @description 207.课程表
  * @author 不知名帅哥
  * @date 2024/6/4 23:27
  * @version 1.0
*/
public class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建图的邻接表表示
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            graph.get(prerequisite[1]).add(prerequisite[0]);
        }

        // 0 = 未访问, 1 = 访问中, 2 = 已访问
        int[] visit = new int[numCourses];

        // 检查每个节点
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(graph, visit, i)) {
                return false;
            }
        }
        return true;
    }

    private boolean hasCycle(List<List<Integer>> graph, int[] visit, int node) {
        if (visit[node] == 1) {
            return true;
        }
        if (visit[node] == 2) {
            return false;
        }
        visit[node] = 1;
        for (int neighbor : graph.get(node)) {
            if (hasCycle(graph, visit, neighbor)) {
                return true;
            }
        }
        visit[node] = 2;
        return false;
    }

    public static void main(String[] args) {
        CourseSchedule cs = new CourseSchedule();
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}};
        System.out.println(cs.canFinish(numCourses, prerequisites)); // 输出: true

        int[][] prerequisites2 = {{1, 0}, {0, 1}};
        System.out.println(cs.canFinish(numCourses, prerequisites2)); // 输出: false
    }
}
